﻿#include <iostream>
#include "LinkedListNode.h"

static LinkedListNode* copy(LinkedListNode* head)
{
	if (!head) return nullptr;

	// 将原先的每个节点的next指向复制自己的新节点，再将新节点的next指向原节点的next节点
	// 然后根据原节点的rand找到新节点的rand
	// 拆分为2个独立的链表

	LinkedListNode* cur = head;
	LinkedListNode* next = nullptr;
	while (cur)
	{
		next = cur->next;
		auto node = new LinkedListNode(cur->value);
		node->next = next;
		cur->next = node;
		cur = next;
	}

	cur = head;
	while (cur)
	{
		auto rand = cur->rand;
		if (rand)
		{
			cur->next->rand = rand->next;
		}

		cur = cur->next->next;
	}

	cur = head;
	LinkedListNode* newHead = cur->next;
	auto newCur = newHead;
	while (cur)
	{
		if (cur->next)
		{
			next = cur->next->next;
			cur->next = next;
			cur = next;
		}
		else
		{
			cur->next = nullptr;
		}


		if (newCur->next)
		{
			next = newCur->next->next;
			newCur->next = next;
			newCur = next;
		}
		else
		{
			newCur->next = nullptr;
			break;
		}
	}

	//printLinkedList(head);
	//printLinkedList(newHead);
	return newHead;
}

static void makeRand(LinkedListNode* head)
{
	auto cur = head;
	LinkedListNode* randCur = nullptr;
	size_t count = 0;
	while (cur)
	{
		++count;
		cur = cur->next;
	}

	cur = head;
	srand((unsigned)time(NULL));
	while (cur)
	{
		int rd = rand() % (count + 1);
		randCur = head;
		if (rd == count)
		{
			cur->rand = nullptr;
		}
		else
		{
			for (int i = 0; i < rd; i++)
			{
				randCur = randCur->next;
			}

			cur->rand = randCur;
		}

		cur = cur->next;
	}
}

// 复制含有随机指针节点的链表
// [题目] 一种特殊的单链表节点类描述如下
// class Node {
//	 int value;
//	 Node next;
//	 Node rand;
//	 Node(int val) {
//		value = val;
//		
// }
//
//
// rand指针是单链表节点结构中新增的指针，rand可能指向链表中的任意一个节点，
// 也可能指向null。给定一个由Node节点类型组成的无环单链表的头结点head，
// 请实现一个函数完成这个链表的复制，并返回复制的新链表的头节点。
// [要求] 时间复杂度O(N), 额外空间复杂度O(1)
int main_CopyNodeExistsRandomPointer()
{
	auto head = new LinkedListNode(1);
	head->next = new LinkedListNode(2);
	head->next->next = new LinkedListNode(3);
	head->next->next->next = new LinkedListNode(4);
	head->next->next->next->next = new LinkedListNode(5);
	head->next->next->next->next->next = new LinkedListNode(6);
	head->next->next->next->next->next->next = new LinkedListNode(7);
	makeRand(head);

	auto newHead = copy(head);

	delLinkedListNode(head);
	delLinkedListNode(newHead);
	return 0;
}